package 数据结构系列;

public class K个一组翻转链表_25 {

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        //区间[a,b)包含k个待反转元素
        ListNode a;
        ListNode b;
        a = b = head;

        for (int i = 0; i < k; i++) {
            //不足k个无需反转
            if (b == null) {
                return head;
            }
            b = b.next;
        }
        //反转前k个元素
        ListNode newHead = reverse(a, b);
        //递归反转后续链表，并且连接起来
        a.next = reverseKGroup(b, k);

        return newHead;
    }

    //反转区间[a,b)的元素
    public ListNode reverse(ListNode a, ListNode b) {
        ListNode pre;
        ListNode cur;
        ListNode next;

        pre = null;
        cur = a;
        next = a;
        while (cur != b) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        //返回反转后的头节点
        return pre;
    }


//    //反转以a为头节点的链表
//    public ListNode reverse(ListNode a) {
//        ListNode pre;
//        ListNode cur;
//        ListNode next;
//
//        pre = null;
//        cur = a;
//        next = a;
//        while (cur != null) {
//            next = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = next;
//        }
//
//        //返回反转后的头节点
//        return pre;
//    }
}
